
#include<iostream>
#include<string>
#include<bitset>
using namespace std;
namespace my_stl
{
    struct BKDRHash
    {
        size_t operator()(const string &s)
        {
            size_t value = 0;
            for (auto ch : s)
            {
                value *= 31;
                value += ch;
            }
            return value;
        }
    };

    struct APHash
    {
        size_t operator()(const string &s)
        {
            size_t hash = 0;
            for (long i = 0; i < s.size(); i++)
            {
                if ((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
                }
            }
            return hash;
        }
    };

    struct DJBHash
    {
        size_t operator()(const string &s)
        {
            size_t hash = 5381;
            for (auto ch : s)
            {
                hash += (hash << 5) + ch;
            }
            return hash;
        }
    };
    struct JSHash
    {
        size_t operator()(const string &s)
        {
            size_t hash = 1315423911;
            for (auto ch : s)
            {
                hash ^= ((hash << 5) + ch + (hash >> 2));
            }
            return hash;
        }
    };

    template <size_t M, class T = string, class Hashfunc1 = BKDRHash, class Hashfunc2 = APHash, class Hashfun3 = DJBHash>
    class BloomFilter
    {
    public:
        // 构造函数
        BloomFilter() {} // 默认构造函数足够使用
        // 设置当前位置
        void set(const T &key)
        {
            size_t hash1 = Hashfun1()(key) % M;
            size_t hash2 = Hashfun2()(key) % M;
            size_t hash3 = Hashfun3()(key) % M;
            _bs.set(hash1);
            _bs.set(hash2);
            _bs.set(hash3);
        }

        // 检测是否存在
        bool Test(const T &key)
        {
            size_t hash1 = Hashfun1()(key) % M;
            if (_bs.test(hash1) == false)
            {
                return false;
            }
            size_t hash2 = Hashfun2()(key) % M;
            if (_bs.test(hash2) == false)
            {
                return false;
            }
            size_t hash2 = Hashfun3()(key) % M;
            if (_bs.test(hash3) == false)
            {
                return false;
            }

            // 存在误判
            return true;
        }

    private:
        bitset<M> _bs;
    };
}